Ta có một tập huấn luyện D {\displaystyle {\mathcal {D}}} gồm n điểm có dạng

D = { ( x i , y i ) ∣ x i ∈ R p , y i ∈ { − 1 , 1 } } i = 1 n {\displaystyle {\mathcal {D}}=\left\{(\mathbf {x} _{i},y_{i})\mid \mathbf {x} _{i}\in \mathbb {R} ^{p},\,y_{i}\in \{-1,1\}\right\}_{i=1}^{n}}

với yi mang giá trị 1 hoặc −1, xác định lớp của điểm x i {\displaystyle \mathbf {x} _{i}} . Mỗi x i {\displaystyle \mathbf {x} _{i}} là một vectơ thực p-chiều. Ta cần tìm siêu phẳng có lề lớn nhất chia tách các điểm có y i = 1 {\displaystyle y_{i}=1} và các điểm có y i = − 1 {\displaystyle y_{i}=-1} . Mỗi siêu phẳng đều có thể được viết dưới dạng một tập hợp các điểm x {\displaystyle \mathbf {x} } thỏa mãn

Siêu phẳng với lề cực đại cho một SVM phân tách dữ liệu thuộc hai lớp. Các ví dụ nằm trên lề được gọi là các vectơ hỗ trợ. w ⋅ x − b = 0 , {\displaystyle \mathbf {w} \cdot \mathbf {x} -b=0,\,}

với ⋅ {\displaystyle \cdot } ký hiệu cho tích vô hướng và w {\displaystyle {\mathbf {w} }} là một vectơ pháp tuyến của siêu phẳng. Tham số b ‖ w ‖ {\displaystyle {\tfrac {b}{\|\mathbf {w} \|}}} xác định khoảng cách giữa gốc tọa độ và siêu phẳng theo hướng vectơ pháp tuyến w {\displaystyle {\mathbf {w} }} .

Chúng ta cần chọn w {\displaystyle {\mathbf {w} }} và b {\displaystyle b} để cực đại hóa lề, hay khoảng cách giữa hai siêu mặt song song ở xa nhau nhất có thể trong khi vẫn phân chia được dữ liệu. Các siêu mặt ấy được xác định bằng

w ⋅ x − b = 1 {\displaystyle \mathbf {w} \cdot \mathbf {x} -b=1\,}

và

w ⋅ x − b = − 1. {\displaystyle \mathbf {w} \cdot \mathbf {x} -b=-1.\,}

Để ý rằng nếu dữ liệu huấn luyện có thể được chia tách một cách tuyến tính, thì ta có thể chọn hai siêu phẳng của lề sao cho không có điểm nào ở giữa chúng và sau đó tăng khoảng cách giữa chúng đến tối đa có thể. Bằng hình học, ta tìm được khoảng cách giữa hai siêu phẳng là 2 ‖ w ‖ {\displaystyle {\tfrac {2}{\|\mathbf {w} \|}}} . Vì vậy ta muốn cực tiểu hóa giá trị ‖ w ‖ {\displaystyle \|\mathbf {w} \|} . Để đảm bảo không có điểm dữ liệu nào trong lề, ta thêm vào các điều kiện sau:

Với mỗi i {\displaystyle i} ta có

w ⋅ x i − b ≥ 1  cho  x i {\displaystyle \mathbf {w} \cdot \mathbf {x} _{i}-b\geq 1\qquad {\text{ cho }}\mathbf {x} _{i}} thuộc lớp thứ nhất

hoặc

w ⋅ x i − b ≤ − 1  cho  x i {\displaystyle \mathbf {w} \cdot \mathbf {x} _{i}-b\leq -1\qquad {\text{ cho }}\mathbf {x} _{i}} thuộc lớp thứ hai

Có thể viết gọn lại như sau với mọi 1 ≤ i ≤ n {\displaystyle 1\leq i\leq n} :

y i ( w ⋅ x i − b ) ≥ 1 , ( 1 ) {\displaystyle y_{i}(\mathbf {w} \cdot \mathbf {x} _{i}-b)\geq 1,\qquad \qquad (1)}

Tóm lại, ta có bài toán tối ưu hóa sau:

Cực tiểu hóa (theo w , b {\displaystyle {\mathbf {w} ,b}} )

‖ w ‖ {\displaystyle \|\mathbf {w} \|}

với điều kiện (với mọi i = 1 , … , n {\displaystyle i=1,\dots ,n} )

y i ( w ⋅ x i − b ) ≥ 1. {\displaystyle y_{i}(\mathbf {w} \cdot \mathbf {x_{i}} -b)\geq 1.\,}

Dạng ban đầu

Bài toán tối ưu ở mục trên tương đối khó giải vì hàm mục tiêu phụ thuộc vào ||w||, là một hàm có khai căn. Tuy nhiên có thể thay ||w|| bằng hàm mục tiêu 1 2 ‖ w ‖ 2 {\displaystyle {\tfrac {1}{2}}\|\mathbf {w} \|^{2}} (hệ số 1/2 để tiện cho các biến đổi toán học sau này) mà không làm thay đổi lời giải (lời giải của bài toán mới và bài toán ban đầu có cùng w và b). Đây là một bài toán quy hoạch toàn phương. Cụ thể hơn:

Cực tiểu hóa (theo w , b {\displaystyle {\mathbf {w} ,b}} )

1 2 ‖ w ‖ 2 {\displaystyle {\frac {1}{2}}\|\mathbf {w} \|^{2}}

với điều kiện (với mọi i = 1 , … , n {\displaystyle i=1,\dots ,n} )

y i ( w ⋅ x i − b ) ≥ 1. {\displaystyle y_{i}(\mathbf {w} \cdot \mathbf {x_{i}} -b)\geq 1.}

Bằng cách thêm các nhân tử Lagrange α {\displaystyle {\boldsymbol {\alpha }}} , bài toán trên trở thành

min w , b max α ≥ 0 { 1 2 ‖ w ‖ 2 − ∑ i = 1 n α i [ y i ( w ⋅ x i − b ) − 1 ] } {\displaystyle \min _{\mathbf {w} ,b}\max _{{\boldsymbol {\alpha }}\geq 0}\left\{{\frac {1}{2}}\|\mathbf {w} \|^{2}-\sum _{i=1}^{n}{\alpha _{i}[y_{i}(\mathbf {w} \cdot \mathbf {x_{i}} -b)-1]}\right\}}

nghĩa là ta cần tìm một điểm yên ngựa. Khi đó, tất cả các điểm không nằm trên lề, nghĩa là y i ( w ⋅ x i − b ) − 1 > 0 {\displaystyle y_{i}(\mathbf {w} \cdot \mathbf {x_{i}} -b)-1>0} đều không ảnh hưởng đến giá trị hàm mục tiêu vì ta có thể chọn α i {\displaystyle \alpha _{i}} bằng không.

Có thể giải bài toán này bằng các kĩ thuật thông thường cho quy hoạch toàn phương. Theo điều kiện Karush–Kuhn–Tucker, lời giải có thể được viết dưới dạng tổ hợp tuyến tính của các vectơ luyện tập

w = ∑ i = 1 n α i y i x i . {\displaystyle \mathbf {w} =\sum _{i=1}^{n}{\alpha _{i}y_{i}\mathbf {x_{i}} }.}

Chỉ có một vài α i {\displaystyle \alpha _{i}} nhận giá trị lớn hơn 0. Các điểm x i {\displaystyle \mathbf {x_{i}} } tương ứng là các vectơ hỗ trợ nằm trên lề và thỏa mãn y i ( w ⋅ x i − b ) = 1 {\displaystyle y_{i}(\mathbf {w} \cdot \mathbf {x_{i}} -b)=1} . Từ điều kiện này, ta nhận thấy

w ⋅ x i − b = 1 / y i = y i ⟺ b = w ⋅ x i − y i {\displaystyle \mathbf {w} \cdot \mathbf {x_{i}} -b=1/y_{i}=y_{i}\iff b=\mathbf {w} \cdot \mathbf {x_{i}} -y_{i}}

từ đó ta suy ra được giá trị b {\displaystyle b} . Trên thực tế, một cách thức tốt hơn để tính b {\displaystyle b} là tính giá trị trung bình từ tất cả N S V {\displaystyle N_{SV}} vectơ hỗ trợ:

b = 1 N S V ∑ i = 1 N S V ( w ⋅ x i − y i ) {\displaystyle b={\frac {1}{N_{SV}}}\sum _{i=1}^{N_{SV}}{(\mathbf {w} \cdot \mathbf {x_{i}} -y_{i})}}

Dạng đối ngẫu

Nếu viết điều kiện phân loại dưới dạng đối ngẫu không điều kiện thì sẽ dễ dàng nhận thấy siêu phẳng với lề lớn nhất, và do đó nhiệm vụ phân loại, chỉ phụ thuộc vào các điểm luyện tập nằm trên lề, còn gọi là các vectơ hỗ trợ.

Vì ‖ w ‖ 2 = w ⋅ w {\displaystyle \|\mathbf {w} \|^{2}=w\cdot w} và w = ∑ i = 1 n α i y i x i {\displaystyle \mathbf {w} =\sum _{i=1}^{n}{\alpha _{i}y_{i}\mathbf {x_{i}} }} , ta nhận thấy bài toán đối ngẫu của SVM là chính là bài toán tối ưu hóa sau:

Cực đại hóa (theo α i {\displaystyle \alpha _{i}} )

L ~ ( α ) = ∑ i = 1 n α i − 1 2 ∑ i , j α i α j y i y j x i T x j = ∑ i = 1 n α i − 1 2 ∑ i , j α i α j y i y j k ( x i , x j ) {\displaystyle {\tilde {L}}(\mathbf {\alpha } )=\sum _{i=1}^{n}\alpha _{i}-{\frac {1}{2}}\sum _{i,j}\alpha _{i}\alpha _{j}y_{i}y_{j}\mathbf {x} _{i}^{T}\mathbf {x} _{j}=\sum _{i=1}^{n}\alpha _{i}-{\frac {1}{2}}\sum _{i,j}\alpha _{i}\alpha _{j}y_{i}y_{j}k(\mathbf {x} _{i},\mathbf {x} _{j})}

với điều kiện (với mọi i = 1 , … , n {\displaystyle i=1,\dots ,n} )

α i ≥ 0 , {\displaystyle \alpha _{i}\geq 0,\,}

và điều kiện sau ứng với việc cực tiểu hóa theo b {\displaystyle b}

∑ i = 1 n α i y i = 0. {\displaystyle \sum _{i=1}^{n}\alpha _{i}y_{i}=0.}

Ở đây hàm hạt nhân được định nghĩa là k ( x i , x j ) = x i ⋅ x j {\displaystyle k(\mathbf {x} _{i},\mathbf {x} _{j})=\mathbf {x} _{i}\cdot \mathbf {x} _{j}} .

Sau khi giải xong, có thể tính w {\displaystyle \mathbf {w} } từ các giá trị α {\displaystyle \alpha } tìm được như sau:

w = ∑ i α i y i x i . {\displaystyle \mathbf {w} =\sum _{i}\alpha _{i}y_{i}\mathbf {x} _{i}.}